package 算法模板;

import java.util.Arrays;

/**
 * KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，
 * 因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹
 * 配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现
 * 就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时
 * 间复杂度O(m+n)。                       --来源 百度百科
 */
public class KMP字符串匹配 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(getNextArray("abcabe")));
        System.out.println(kmp("dfddfs", "dfs"));

    }

    // rabcabe
    //  abcabh
    // 当 str[6]!=childStr[5] 时
    // 有 str[1-5]=childStr[0-4]  j=5 且 最长相等前缀后缀长度为2
    // rabcabe
    //     abcabh  j=2

    /**
     * 前缀定义：包含字符串开头字符的连续子串
     * 后缀定义：包含字符串结尾字符的连续字串
     * 核心思路：
     * 利用匹配失败后的信息，如果 str[i] != matchStr[j] ，那么
     * str中一定存在，i之前一定存在j个数使得，str[i-j,i-1] == matchStr[0,j-1]
     * 如果 matchStr[0,j-1] 的最长相等前缀和后缀为 k，那么
     * 将 matchStr 的 j 位置移动到 k 的位置
     */
    public static boolean kmp(String str, String matchStr) {
        int[] nextArray = getNextArray(matchStr);
        int i = 0, j = 0;
        while (i < str.length() && j < matchStr.length()) {
            if (j == -1 || str.charAt(i) == matchStr.charAt(j)) {
                i++;
                j++;
            } else {
                j = nextArray[j];  // 主串索引不变，字串索引变成next[j]
            }
            if (j == matchStr.length()) return true;
        }
        return false;
    }

    public static int[] getNextArray(String matchStr) {
        char[] chars = matchStr.toCharArray();
        int[] next = new int[chars.length];
        // 初始化，索引0的位置为-1，不需要再进行回溯
        next[0] = -1;
        int cur = 0, k = -1;  // 下标为cur的字符前的字符串最长相等前后缀的长度为k
        while (cur < chars.length - 1) {
            if (k == -1 || chars[cur] == chars[k]) {
                next[++cur] = ++k;
            } else {
                // 回溯
                k = next[k];
            }
        }
        return next;
    }

}
